//
//  main.c
//  LinearList
//
//  Created by XAJZ on 2020/3/31.
//  Copyright © 2020 XAJZ. All rights reserved.
//

//此工程主要演示线性表的顺序存储

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

//线性表的最大容量
#define MAXSIZE 100
//操作状态-成功
#define SUCCESS 1
//操作状态-失败
#define ERROR 0

#define TRUE 1
#define FALSE 0

//表内元素的类型 假设为 int
typedef int ItemType;
//返回各个函数的操作码
typedef int Status;

//顺序表
typedef struct {
//    指向一块连续的内存空间来存储数据
    ItemType *data;
//    表的长度
    int length;
}List;

//1.1顺序表的初始化 注意：一般地，我们可以空出表的第一个元素用作“哨兵”。(本示例未使用哨兵)
//在许多算法中，存在“邻居依赖问题”（我自己造的词），在处理当前元素时，要涉及到它旁边那个元素。那如果当前元素是边界元素呢，它没有旁边那个元素，如果不作处理，程序就可能出错；如果对它特别对待，就会增加代码复杂性，还会降低程序效率。应用哨兵，也就是申请若干个多余的元素作为边界元素的邻居，可以完美得解决这个问题。
//同时，哨兵元素可以用来存储一些状态值，或者用作临时变量

Status initList(List *l){
//    开辟一段连续的空间给顺序表
    l->data = malloc(sizeof(ItemType) * MAXSIZE);
//    如果存储分配失败，则退出
    if (!l->data) exit(ERROR);
    
    l->length = 0;
    return SUCCESS;
        
}

//遍历并打印线性表
Status listPrint(List l){
    if (!l.length) {
        printf("Empty list.");
        return ERROR;
    }
    printf("数组输出：");
    for (int i = 0; i < l.length; i++) {
        printf("%d ",l.data[i]);
    }
    printf("\n");
    return SUCCESS;
}


/// 在i位置插入新的元素 e
/// @param l 数组
/// @param i 位置
/// @param e 新元素
Status listInsert(List *l, int i, ItemType e){
//    插入位置是否合法
    if (i < 1 || i > l->length + 1) return ERROR;
//    是否还有剩余空间
    if (l->length == MAXSIZE) return ERROR;
    
    if (i <= l->length) {
        for (int j = l->length-1; j >= i - 1; j--) {
//            将插入位置以及之后的位置向后移动一位
            l->data[j+1] = l->data[j];
        }
    }
//    将新元素放入i位置
    l->data[i-1] = e;
//    长度+1
    l->length++;
    return SUCCESS;
}

/// 删除 i 位置的原素
/// @param l 数组
/// @param i 位置
/// @param e 删除元素带回
Status listDelete(List *l, int i, ItemType *e){
    if (i < 1 || i > l->length ) return ERROR;
//    保留原值
    *e = l->data[i-1];
    for (int j = i; j < l->length; j++) {
//        被删除元素之后的元素向前移动一位
        l->data[j-1] = l->data[j];
    }
//    表长度减一
    l->length--;
    return SUCCESS;
}


/// 获取某值
/// @param l 列表
/// @param i 位置
/// @param e 获取元素带回
Status listGet(List l, int i, ItemType *e){
    if (i < 1 || i > l.length + 1) return ERROR;
    *e = l.data[i-1];
    return SUCCESS;
}

int main(int argc, const char *argv[]){
    List l;
    Status lStatus;
    ItemType e;
    
    lStatus = initList(&l);
    printf("初始化后：l.length = %d \n",l.length);
    
    for (int i = 1; i < 7; i++) {
        listInsert(&l, 1, i);
    }
    printf("插入后：l.length = %d \n",l.length);
    listPrint(l);
    
    listDelete(&l, 1, &e);
    printf("删除后：l.length = %d \n",l.length);
    listPrint(l);
    

    listGet(l, 2, &e);
    printf("取出元素为：%d \n",e);
}

